//
//  BreadthFirstSearch.h
//  GraphTheory
//
//  Created by 刘振舟 on 2024/7/16.
//

#ifndef BreadthFirstSearch_h
#define BreadthFirstSearch_h
#include <queue>
#include <unordered_set>
#include <ctype.h>
#include "Tree.h"

using namespace std;

class BreadthFirstSearchSolution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, -1, 0, 1};
        queue<tuple<int, int, int>> que;
        que.emplace(entrance[0], entrance[1], 0);
        maze[entrance[0]][entrance[1]] = '+';
        size_t m = maze.size(), n = maze[0].size();
        
        while (!que.empty()) {
            auto [x, y, d] = que.front();
            que.pop();
            for (int i = 0; i < 4; ++i) {
                int newX = x + dx[i], newY = y + dy[i];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && maze[newX][newY] == '.') {
                    if (newX == 0 || newX == m - 1 || newY == 0 || newY == n - 1) {
                        return d + 1;
                    }
                    maze[newX][newY] = '+';
                    que.emplace(newX, newY, d + 1);
                }
            }
        }
        
        return -1;
    }
    
    int shortestBridge(vector<vector<int>>& grid) {
        queue<pair<int, int>> que;
        queue<pair<int, int>> isLand;
        size_t n = grid.size();
        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, -1, 0, 1};
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    que.emplace(i, j);
                    grid[i][j] = -1;
                    
                    while (!que.empty()) {
                        auto&& [x, y] = que.front();
                        isLand.emplace(x, y);
                        que.pop();
                        
                        for (int k = 0; k < 4; ++k) {
                            int newX = x + dx[k], newY = y + dy[k];
                            if (newX >= 0 && newX < n && newY >= 0 && newY < n && grid[newX][newY] == 1) {
                                que.emplace(newX, newY);
                                grid[newX][newY] = -1;
                            }
                        }
                    }
                    
                    int step = 0;
                    while (!isLand.empty()) {
                        size_t level_size = isLand.size();
                        
                        for (int k = 0; k < level_size; ++k) {
                            auto&& [x, y] = isLand.front();
                            isLand.pop();
                            
                            for (int m = 0; m < 4; ++m) {
                                int newX = x + dx[m], newY = y + dy[m];
                                if (newX >= 0 && newX < n && newY >= 0 && newY < n) {
                                    if (grid[newX][newY] == 1) {
                                        return step;
                                    } else if (grid[newX][newY] == 0) {
                                        isLand.emplace(newX, newY);
                                        grid[newX][newY] = -1;
                                    }
                                }
                            }
                        }
                        ++step;
                    }
                }
            }
        }
        return 0;
    }
    
    
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> bankSet(bank.begin(), bank.end());
        if (startGene == endGene) {
            return 0;
        }
        if (!bankSet.contains(endGene)) {
            return -1;
        }
        
        queue<string> que;
        que.push(startGene);
        bankSet.erase(startGene);
        int step = 1;
        char genes[] = {'A', 'C', 'G', 'T'};
        while (!que.empty()) {
            size_t levelSize = que.size();
            for (int i = 0; i < levelSize; ++i) {
                auto cur = que.front();
                que.pop();
                for (int j = 0; j < 8; ++j) {
                    char x = cur[j];
                    for (auto& y : genes) {
                        if (x != y) {
                            string next = cur;
                            next[j] = y;
                            if (bankSet.contains(next)) {
                                if (next == endGene) {
                                    return step;
                                }
                                que.push(next);
                                bankSet.erase(next);
                            }
                        }
                    }
                }
            }
            ++step;
        }
        return -1;
    }
    
    
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int nodeNum = 0;
        unordered_map<string, int> wordId;
        vector<vector<int>> edges;
        
        function<void(string)> addWord = [&](string word) {
            if (!wordId.contains(word)) {
                wordId[word] = nodeNum++;
                edges.emplace_back();
            }
        };
        
        function<void(string)> addEdge = [&](string word) {
            addWord(word);
            int id1 = wordId[word];
            for (char& it : word) {
                char tmp = it;
                it = '*';
                addWord(word);
                int id2 = wordId[word];
                edges[id1].push_back(id2);
                edges[id2].push_back(id1);
                it = tmp;
            }
        };
        
        for (string word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.contains(endWord)) {
            return 0;
        }
        
        vector<int> disBegin(nodeNum, INT_MAX);
        int beginId = wordId[beginWord];
        disBegin[beginId] = 0;
        queue<int> queBegin;
        queBegin.push(beginId);
        
        vector<int> disEnd(nodeNum, INT_MAX);
        int endId = wordId[endWord];
        disEnd[endId] = 0;
        queue<int> queEnd;
        queEnd.push(endId);
        
        while (!queBegin.empty() && !queEnd.empty()) {
            size_t queBeginSize = queBegin.size();
            for (int i = 0; i < queBeginSize; ++i) {
                int nodeBegin = queBegin.front();
                queBegin.pop();
                if (disEnd[nodeBegin] != INT_MAX) {
                    return (disBegin[nodeBegin] + disEnd[nodeBegin]) / 2 + 1;
                }
                for (int& it : edges[nodeBegin]) {
                    if (disBegin[it] == INT_MAX) {
                        disBegin[it] = disBegin[nodeBegin] + 1;
                        queBegin.push(it);
                    }
                }
            }
            
            size_t queEndSize = queEnd.size();
            for (int i = 0; i < queEndSize; ++i) {
                int nodeEnd = queEnd.front();
                queEnd.pop();
                if (disBegin[nodeEnd] != INT_MAX) {
                    return (disBegin[nodeEnd] + disEnd[nodeEnd]) / 2 + 1;
                }
                for (int& it : edges[nodeEnd]) {
                    if (disEnd[it] == INT_MAX) {
                        disEnd[it] = disEnd[nodeEnd] + 1;
                        queEnd.push(it);
                    }
                }
            }
        }
        
        return 0;
    }


    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int direction[4][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };
        size_t m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n));
        vector<vector<bool>> visited(m, vector<bool>(n));

        queue<pair<int, int>> que;
        for (size_t i = 0; i < m; i++)
        {
            for (size_t j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    que.emplace(i, j);
                    visited[i][j] = true;
                }
            }
        }

        while (!que.empty()) {
            auto &[x, y] = que.front();
            que.pop();
            for (auto &[dx, dy] : direction) {
                int newX = x + dx, newY = y + dy;
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
                    dist[newX][newY] = dist[x][y] + 1;
                    visited[newX][newY] = true;
                    que.emplace(newX, newY);
                }
            }
        }
        return dist;

    }


    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if (grid[0][0] == 1)
            return -1;

        size_t n = grid.size();
        vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
        dist[0][0] = 1;
        queue<pair<int, int>> que;
        que.emplace(0, 0);

        while (!que.empty()) {
            auto [x, y] = que.front();
            que.pop();
            if (x == n - 1 && y == n -1)
            {
                return dist[x][y];
            }

            for (int dx = -1; dx <= 1; dx++)
            {
                for (int dy = -1; dy <= 1; ++dy) {
                    int newX = x + dx, newY = y + dy;
                    if (newX < 0 || newX >= n || newY < 0 || newY >= n)
                        continue;
                    if (grid[newX][newY] == 1 || dist[newX][newY] <= dist[x][y] + 1)
                    {
                        continue;
                    }
                    dist[newX][newY] = dist[x][y] + 1;
                    que.emplace(newX, newY);
                }
            }
        }
        return -1;
    }
    
    
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        unordered_map<int, TreeNode*> parents;
        vector<int> ans;
        
        function<void(TreeNode*)> findParents = [&](TreeNode* root) {
            if (root->left) {
                parents[root->left->val] = root;
                findParents(root->left);
            }
            if (root->right) {
                parents[root->right->val] = root;
                findParents(root->right);
            }
        };
        
        function<void(TreeNode*, TreeNode*, int)> findAns = [&](TreeNode* from, TreeNode* node, int depth) {
            if (node == nullptr) {
                return;
            }
            if (depth == k) {
                ans.push_back(node->val);
                return;
            }
            if (node->left != from) {
                findAns(node, node->left, depth + 1);
            }
            if (node->right != from) {
                findAns(node, node->right, depth + 1);
            }
            if (parents[node->val] != from) {
                findAns(node, parents[node->val], depth + 1);
            }
        };
        
        findParents(root);
        findAns(nullptr, target, 0);
        return ans;
    }
    
    
    int shortestPathAllKeys(vector<string>& grid) {
        size_t m = grid.size(), n = grid[0].size();
        int directions[][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        int sx, sy;
        unordered_map<char, int> key_to_idx;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '@') {
                    sx = i;
                    sy = j;
                } else if (islower(grid[i][j])) {
                    if (!key_to_idx.contains(grid[i][j])) {
                        size_t idx = key_to_idx.size();
                        key_to_idx[grid[i][j]] = idx;
                    }
                }
            }
        }
        
        queue<tuple<int, int, int>> que;
        que.emplace(sx, sy, 0);
        int keySize = key_to_idx.size();
        vector<vector<vector<int>>> dist(m, vector<vector<int>>(n, vector<int>(1 << keySize, -1)));
        dist[sx][sy][0] = 0;
        
        while (!que.empty()) {
            auto [x, y, mask] = que.front();
            que.pop();
            
            for (int i = 0; i < 4; ++i) {
                int nx = x + directions[i][0], ny = y + directions[i][1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] != '#') {
                    char ch = grid[nx][ny];
                    if (ch == '.' || ch == '@') {
                        if (dist[nx][ny][mask] == -1) {
                            dist[nx][ny][mask] = dist[x][y][mask] + 1;
                            que.emplace(nx, ny, mask);
                        }
                    } else if (islower(ch)) {
                        int idx = key_to_idx[ch];
                        int new_mask = (mask | (1 << idx));
                        if (dist[nx][ny][new_mask] == -1) {
                            dist[nx][ny][new_mask] = dist[x][y][mask] + 1;
                            if (new_mask == ((1 << keySize) - 1)) {
                                return dist[nx][ny][new_mask];
                            }
                            que.emplace(nx, ny, new_mask);
                        }
                    } else {
                        int idx = key_to_idx[tolower(ch)];
                        int key = (mask & (1 << idx));
                        if (key && dist[nx][ny][mask] == -1) {
                            dist[nx][ny][mask] = dist[x][y][mask] + 1;
                            que.emplace(nx, ny, mask);
                        }
                    }
                }
            }
        }
        return -1;
    }
};
#endif /* BreadthFirstSearch_h */
